package com.zlsy.learning.leetcode.stack.s844;

/**
 * @author zhouliang
 * @date 2020/8/11 16:35
 *     <p>双指针
 *     <p>反向遍历字符串，如果遍历到一个退格符，那么再往左第一个非退格字符将会被删除，剩余未被删除的字符就是最终的字符串。
 */
public class BackspaceCompare {

  public static boolean backspaceCompare(String S, String T) {
    int i = S.length() - 1, j = T.length() - 1;
    int skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
      while (i >= 0) {
        if (S.charAt(i) == '#') {
          skipS++;
          i--;
        } else if (skipS > 0) {
          skipS--;
          i--;
        } else {
          break;
        }
      }
      while (j >= 0) {
        if (T.charAt(j) == '#') {
          skipT++;
          j--;
        } else if (skipT > 0) {
          skipT--;
          j--;
        } else {
          break;
        }
      }
      if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) {
        return false;
      }
      if ((i >= 0) != (j >= 0)) {
        return false;
      }
      i--;
      j--;
    }
    return true;
  }

  public static void main(String[] args) {
    //    String S = "a#c", T = "b";
    String S = "ab#c", T = "ad#c";
    boolean b = backspaceCompare(S, T);
    System.out.println(b);
  }
}
